home *** CD-ROM | disk | FTP | other *** search
/ Aminet 52 / Aminet 52 (2002)(GTI - Schatztruhe)[!][Dec 2002].iso / Aminet / game / think / AmiChess.lha / AmiChess / src / book.c < prev    next >
C/C++ Source or Header  |  2002-10-31  |  10KB  |  429 lines
  1. #include <clib/alib_protos.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <errno.h>
  6. #include "common.h"
  7. #include "book.h"
  8.  
  9. #define MAXMOVES 200
  10. #define MAXMATCH 100
  11.  
  12. static int bookcnt;
  13. static HashType posshash[MAXMOVES];
  14.  
  15. static int book_allocated=0;
  16.  
  17. #define MAGIC_LENGTH 5
  18.  
  19. static const char magic_str[]="\x42\x23\x08\x15\x03";
  20.  
  21. static int check_magic(FILE *f)
  22. {
  23. char buf[MAGIC_LENGTH];
  24. return fread(&buf,1,MAGIC_LENGTH,f)==MAGIC_LENGTH&&memcmp(buf,magic_str,MAGIC_LENGTH)==0;
  25. }
  26.  
  27. static int write_magic(FILE *f)
  28. {
  29. return (fwrite(&magic_str,1,MAGIC_LENGTH,f)!=MAGIC_LENGTH)?BOOK_EIO:BOOK_SUCCESS;
  30. }
  31.  
  32. static int write_size(FILE *f,unsigned int size)
  33. {
  34. unsigned char sizebuf[4];
  35. int k;
  36. for(k=0;k<4;k++) sizebuf[k]=(size>>((3-k)*8))&0xff;
  37. if(fwrite(&sizebuf,sizeof(sizebuf),1,f)==1) return BOOK_SUCCESS;
  38. return BOOK_EIO;
  39. }
  40.  
  41. static unsigned int read_size(FILE *f)
  42. {
  43. unsigned char sizebuf[4];
  44. unsigned int size=0;
  45. int k;
  46. if(fread(&sizebuf,sizeof(sizebuf),1,f)!=1) return 0;
  47. for(k=0;k<4;k++) size=(size<<8)|sizebuf[k];
  48. return size;
  49. }
  50.  
  51. #define MAX_DIGEST_BITS 20
  52.  
  53. static int digest_bits;
  54.  
  55. #define DIGEST_SIZE (1UL<<digest_bits)
  56. #define DIGEST_MASK (DIGEST_SIZE-1)
  57.  
  58. static struct hashtype
  59. {
  60. unsigned short wins;
  61. unsigned short losses;
  62. unsigned short draws;
  63. HashType key;
  64. } *bookpos;
  65.  
  66. #ifdef __STORM__
  67. __inline int is_empty(unsigned int index)
  68. #else
  69. static inline int is_empty(unsigned int index)
  70. #endif
  71. {
  72. return bookpos[index].key==0&&bookpos[index].wins==0&&bookpos[index].draws==0&&bookpos[index].losses==0;
  73. }
  74.  
  75. #define DIGEST_START(i,key) ((i)=(key)&DIGEST_MASK)
  76. #define DIGEST_MATCH(i,the_key) ((the_key)==bookpos[i].key)
  77. #define DIGEST_EMPTY(i)is_empty(i)
  78. #define DIGEST_COLLISION(i,key) (!DIGEST_MATCH(i,key)&&!DIGEST_EMPTY(i))
  79. #define DIGEST_NEXT(i,key) ((i)=((i)+(((key)>>digest_bits)|1))&DIGEST_MASK)
  80.  
  81. static int bookhashcollisions=0;
  82.  
  83. #define DIGEST_LIMIT (0.95*DIGEST_SIZE)
  84.  
  85. static unsigned char buf[2+2+2+8];
  86.  
  87. static const int wins_off=0;
  88. static const int losses_off=2;
  89. static const int draws_off=4;
  90. static const int key_off=6;
  91.  
  92. static void buf_to_book()
  93. {
  94. HashType key;
  95. unsigned int i;
  96. key=((unsigned long long)buf[key_off]<<56)|
  97.     ((unsigned long long)buf[key_off+1]<<48)|
  98.     ((unsigned long long)buf[key_off+2]<<40)|
  99.     ((unsigned long long)buf[key_off+3]<<32)|
  100.     ((unsigned long long)buf[key_off+4]<<24)|
  101.     ((unsigned long long)buf[key_off+5]<<16)|
  102.     ((unsigned long long)buf[key_off+6]<<8)|
  103.     ((unsigned long long)buf[key_off+7]);
  104. for(DIGEST_START(i,key);DIGEST_COLLISION(i,key);DIGEST_NEXT(i,key)) bookhashcollisions++;
  105. bookpos[i].wins+=(buf[wins_off]<<8)|buf[wins_off+1];
  106. bookpos[i].draws+=(buf[draws_off]<<8)|buf[draws_off+1];
  107. bookpos[i].losses+=(buf[losses_off]<<8)|buf[losses_off+1];
  108. bookpos[i].key=key;
  109. }
  110.  
  111. static void book_to_buf(unsigned int index)
  112. {
  113. int k;
  114. for(k=0;k<2;k++)
  115.     {
  116.     int k1=(1-k)*8;
  117.     buf[wins_off+k]=(bookpos[index].wins>>k1)&0xff;
  118.     buf[draws_off+k]=(bookpos[index].draws>>k1)&0xff;
  119.     buf[losses_off+k]=(bookpos[index].losses>>k1)&0xff;
  120.     }
  121. for(k=0;k<8;k++) buf[key_off+k]=((bookpos[index].key)>>((7-k)*8))&0xff;
  122. }
  123.  
  124. static int compare(const void *aa,const void *bb)
  125. {
  126. int ret;
  127. const leaf *a=(const leaf *)aa;
  128. const leaf *b=(const leaf *)bb;
  129. if(b->score>a->score) ret=1;
  130. else if(b->score<a->score) ret=-1;
  131. else ret=0;
  132. return ret;
  133. }
  134.  
  135. static int read_book(FILE *f)
  136. {
  137. if(book_allocated)
  138.     {
  139.     free(bookpos);
  140.     book_allocated=0;
  141.     }
  142. bookpos=(struct hashtype *)calloc(DIGEST_SIZE,sizeof(struct hashtype));
  143. if(!bookpos) return BOOK_ENOMEM;
  144. book_allocated=1;
  145. bookcnt=0;
  146. bookhashcollisions=0;
  147. while(fread(&buf,sizeof(buf),1,f)==1)
  148.     {
  149.     buf_to_book();
  150.     bookcnt++;
  151.     }
  152. return BOOK_SUCCESS;
  153. }
  154.  
  155. int BookBuilderOpen()
  156. {
  157. FILE *rfp,*wfp;
  158. int res;
  159. char text[100];
  160. if(rfp=fopen(BOOKRUN,"rb"))
  161.     {
  162.     DoMethod(mui_app,MUIM_Chess_ShowThinking,"Opened existing book!");
  163.     if(!check_magic(rfp))
  164.         {
  165. /*        fprintf(stderr,"File %s does not conform to the current format.\nConsider rebuilding your book.\n",BOOKRUN); */
  166.         return BOOK_EFORMAT;
  167.         }
  168.     digest_bits=MAX_DIGEST_BITS;
  169.     read_size(rfp);
  170.     res=read_book(rfp);
  171.     fclose(rfp);
  172.     if(res!=BOOK_SUCCESS)
  173.         {
  174.         fclose(rfp);
  175.         return res;
  176.         }
  177.     sprintf(text,"Read %d book positions. Got %d hash collisions.",bookcnt,bookhashcollisions);
  178.     DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  179.     }
  180. else
  181.     {
  182.     wfp=fopen(BOOKRUN,"w+b");
  183.     if(wfp==NULL)
  184.         {
  185. /*        fprintf(stderr,"Could not create %s file: %s\n",BOOKRUN,strerror(errno)); */
  186.         return BOOK_EIO;
  187.         }
  188.     if(write_magic(wfp)!=BOOK_SUCCESS)
  189.         {
  190. /*        fprintf(stderr,"Could not write to %s: %s\n",BOOKRUN,strerror(errno)); */
  191.         return BOOK_EIO;
  192.         }
  193.     if(fclose(wfp))
  194.         {
  195. /*        fprintf(stderr,"Could not write to %s: %s\n",BOOKRUN,strerror(errno)); */
  196.         return BOOK_EIO;
  197.         }
  198.     sprintf(text,"Created new book %s!",BOOKRUN);
  199.     DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  200.     if(!(rfp=fopen(BOOKRUN,"rb")))
  201.         {
  202. /*        fprintf(stderr,"Could not open %s for reading: %s\n",BOOKRUN,strerror(errno)); */
  203.         return BOOK_EIO;
  204.         }
  205.     digest_bits=MAX_DIGEST_BITS;
  206.     if(read_book(wfp)==BOOK_ENOMEM) return BOOK_ENOMEM;
  207.     }
  208. return BOOK_SUCCESS;
  209. }
  210.  
  211. int BookBuilder(short result,short side)
  212. {
  213. unsigned int i;
  214. if(GameCnt/2+1>=BOOKDEPTH) return BOOK_EMIDGAME;
  215. CalcHashKey();
  216. for(DIGEST_START(i,HashKey);;DIGEST_NEXT(i,HashKey))
  217.     {
  218.     if(DIGEST_MATCH(i,HashKey))
  219.         {
  220.         existpos++;
  221.         break;
  222.         }
  223.     else if(DIGEST_EMPTY(i))
  224.         {
  225.         if(bookcnt>DIGEST_LIMIT) return BOOK_EFULL;
  226.         bookpos[i].key=HashKey;
  227.         newpos++;
  228.         bookcnt++;
  229.         break;
  230.         }
  231.     else bookhashcollisions++;
  232.     }
  233. if(side==white)
  234.     {
  235.     if(result==R_WHITE_WINS) bookpos[i].wins++;
  236.     else if(result==R_BLACK_WINS)
  237.     bookpos[i].losses++;
  238.     else if(result==R_DRAW) bookpos[i].draws++;
  239.     }
  240. else
  241.     {
  242.     if(result==R_WHITE_WINS) bookpos[i].losses++;
  243.     else if(result==R_BLACK_WINS) bookpos[i].wins++;
  244.     else if(result==R_DRAW) bookpos[i].draws++;
  245.     }
  246. return BOOK_SUCCESS;
  247. }
  248.  
  249. int BookBuilderClose()
  250. {
  251. FILE *wfp;
  252. unsigned int i;
  253. int errcode=BOOK_SUCCESS;
  254. char text[100];
  255. if(!(wfp=fopen(BOOKRUN,"wb")))
  256.     {
  257.     errcode=BOOK_EIO;
  258.     goto bailout_noclose;
  259.     }
  260. if(write_magic(wfp)!=BOOK_SUCCESS)
  261.     {
  262.     errcode=BOOK_EIO;
  263.     goto bailout;
  264.     }
  265. if(write_size(wfp,bookcnt)!=BOOK_SUCCESS)
  266.     {
  267.     errcode=BOOK_EIO;
  268.     goto bailout;
  269.     }
  270. for(i=0;i<DIGEST_SIZE;i++)
  271.     {
  272.     if(!is_empty(i))
  273.         {
  274.         book_to_buf(i);
  275.         if(fwrite(&buf,sizeof(buf),1,wfp)!=1)
  276.             {
  277.             errcode=BOOK_EIO;
  278.             goto bailout;
  279.             }
  280.         }
  281.     }
  282. sprintf(text,"Got %d hash collisions.",bookhashcollisions);
  283. DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  284.  
  285. bailout:
  286. if(fclose(wfp)) errcode=BOOK_EIO;
  287.  
  288. bailout_noclose:
  289. free(bookpos);
  290. book_allocated=0;
  291. bookloaded=0;
  292. return errcode;
  293. }
  294.  
  295. int BookQuery()
  296. {
  297. int i,j,k,icnt=0,mcnt,found,tot,maxdistribution;
  298. int matches[MAXMATCH] ;
  299. leaf m[MAXMOVES];
  300. leaf pref[MAXMOVES];
  301. struct {
  302. unsigned short wins;
  303. unsigned short losses;
  304. unsigned short draws;
  305. } r[MAXMOVES];
  306. FILE *rfp;
  307. leaf *p;
  308. short side,xside,temp;
  309. unsigned int booksize;
  310. int res;
  311. char text[100];
  312. if(bookloaded&&!book_allocated) return BOOK_ENOBOOK;
  313. if(!bookloaded)
  314.     {
  315.     bookloaded=1;
  316.     if(!(rfp=fopen(BOOKBIN,"rb"))) return BOOK_ENOBOOK;
  317.     sprintf(text,"Read opening book (%s)...",BOOKBIN);
  318.     DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  319.     if(!check_magic(rfp))
  320.         {
  321. /*        fprintf(stderr," File %s does not conform to the current format.\n Consider rebuilding the book.\n\n",BOOKBIN); */
  322.         return BOOK_EFORMAT;
  323.         }
  324.     booksize=read_size(rfp)*1.06;
  325.     for(digest_bits=1;booksize;booksize>>=1) digest_bits++;
  326.     res=read_book(rfp);
  327.     if(res!=BOOK_SUCCESS) return res;
  328.     sprintf(text,"%d hash collisions... ",bookhashcollisions);
  329.     DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  330.     }
  331. mcnt=-1;
  332. side=board.side;
  333. xside=1^side;
  334. TreePtr[2]=TreePtr[1];
  335. GenMoves(1);
  336. FilterIllegalMoves(1);
  337. for(p=TreePtr[1];p<TreePtr[2];p++)
  338.     {
  339.     MakeMove(side,&p->move);
  340.     m[icnt].move=p->move;
  341.     posshash[icnt]=HashKey;
  342.     icnt++;
  343.     UnmakeMove(xside,&p->move);
  344.     }
  345. for(i=0;i<icnt;i++)
  346.     {
  347.     for(DIGEST_START(j,posshash[i]);!DIGEST_EMPTY(j);DIGEST_NEXT(j,posshash[i]))
  348.         {
  349.         if(DIGEST_MATCH(j,posshash[i]))
  350.             {
  351.             found=0;
  352.             for(k=0;k<mcnt;k++) if(matches[k]==i)
  353.                 {
  354.                 found=1;
  355.                 break;
  356.                 }
  357.             if(!found)
  358.                 {
  359.                 matches[++mcnt]=i;
  360.                 pref[mcnt].move=m[matches[mcnt]].move;
  361.                 r[i].losses=bookpos[j].losses;
  362.                 r[i].wins=bookpos[j].wins;
  363.                 r[i].draws=bookpos[j].draws;
  364.                 pref[mcnt].score=m[i].score=100*(r[i].wins+(r[i].draws/2))/(MAX(r[i].wins+r[i].losses+r[i].draws,1))+r[i].wins/2;
  365.                 }
  366.             if(mcnt>=MAXMATCH)
  367.                 {
  368.                 sprintf(text,"Too many matches in book.");
  369.                 DoMethod(mui_app,MUIM_Chess_ShowThinking,text);
  370.                 goto fini;
  371.                 }
  372.             break;
  373.             }
  374.         }
  375.     }
  376.  
  377. fini:  
  378. if(mcnt==-1) return BOOK_ENOMOVES;
  379. k=0;
  380. if(mcnt+1)
  381.     {
  382.     if(bookmode==BOOKRAND)
  383.         {
  384.         k=rand();
  385.         k=k%(mcnt+1);
  386.         RootPV=m[matches[k]].move;
  387.         printf("\n(Random picked move #%d %s%s from above list)\n",k,algbr[FROMSQ(RootPV)],algbr[TOSQ(RootPV)]);
  388.         tot=r[matches[k]].wins+r[matches[k]].draws+r[matches[k]].losses;
  389.         if(tot) printf("B p=%2.0f\n",100.0*(r[matches[k]].wins+r[matches[k]].draws)/tot);
  390.         else printf("p=NO EXPERIENCES\n");
  391.         }
  392.     else if(bookmode==BOOKBEST)
  393.         {
  394.         qsort(&pref,mcnt+1,sizeof(leaf),compare);
  395.         RootPV=pref[0].move;
  396.         }
  397.     else if(bookmode==BOOKWORST)
  398.         {
  399.         qsort(&pref,mcnt+1,sizeof(leaf),compare);
  400.         RootPV=pref[mcnt].move;
  401.         }
  402.     else if(bookmode==BOOKPREFER)
  403.         {
  404.         qsort(&pref,mcnt+1,sizeof(leaf),compare);
  405.         for(i=0;i<=mcnt;i++)
  406.             {
  407.             m[i].move=pref[i].move;
  408.             }
  409.         temp=(bookfirstlast>mcnt+1?mcnt+1:bookfirstlast);
  410.         maxdistribution=0;
  411.         for(i=0;i<temp;i++) maxdistribution+=pref[i].score;
  412.         if(!maxdistribution) return BOOK_ENOMOVES;
  413.         k=rand()%maxdistribution;
  414.         maxdistribution=0;
  415.         for(i=0;i<temp;i++)
  416.             {
  417.             maxdistribution+=pref[i].score;
  418.             if(k>=maxdistribution-pref[i].score&&k<maxdistribution)
  419.                 {
  420.                 k=i;
  421.                 RootPV=m[k].move;
  422.                 break;
  423.                 }
  424.             }
  425.         }
  426.     }
  427. return BOOK_SUCCESS;
  428. }
  429.